Selepas lebih kurang tiga tahun Search dibekukan, pada penghujung tahun 2003, Amy, Kid, Din dan Nasir akhirnya mengambil keputusan untuk bersatu semula dengan menjemput seluruh pelusuk wartawan hiburan mengadakan sidang media secara besaran bagi merancang sebuah konsert reunion berskala besar yang disaksikan oleh artis dari Indonesia kumpulan Godbless di Stadium Merdeka Kuala Lumpur dan bakal muncul album terbaharu yang berjudul Empire Garden. Sidang media itu juga turut dihadiri kumpulan Wings untuk memberi sokongan terhadap Search termasuk juga Search memperkenalkan Lola (bekas pemain drum XPDC) adalah selaku pemain drum baharu Search bagi menggantikan tempat Yazit. Beberapa hari kemudian ia dilanda sedikit kontroversi terhadap Yazit yang ditemui oleh wartawan media hiburan mendakwa dirinya (Yazit) tidak dimaklum, tidak dijemput dan tidak mengetahui langsung tentang berita Search yang bakal mengadakan konsert besar reunion itu, ditambah pula Yazit masih yakin bahawa nama kumpulan Search itu adalah hak beliau dan juga sebagai pengasas. Yazit tidak restu dengan konsert yang dirancang oleh Search tanpa pengetahuannya. Yazit yang tersinggung mendesak Search supaya membatalkan konsert yang dirancang oleh mereka sehingga Yazit mahu melantik beberapa orang peguam dan bakal menfailkan saman terhadap Search di mahkamah. Yazit tidak ketinggalan menunjuk bukti terhadap wartawan media hiburan berhubung surat perletakan jawatan Amy yanh ditandatangani olehnya sebagai penyanyi Search pada tahun 1998. Tarikh bakal konsert reunion itu telah ditunda beberapa kali, namun Search menafikan konsert itu bakal dibatalkan kerana kontroversi saman oleh Yazit. Kerana peminat Search merindui aksi-aksi Search setelah mereka bubarkan nama Search pada tahun 2001. Nama Search dihidupkan kembali dengan dibarisi ahli kumpulan iaitu Amy, Kid, Din, Nasir dan Lola telah mengadakan malam bersejarah dengan sebuah konsert reunion Evolusi Lagenda Rock Search di Stadium Merdeka Kuala Lumpur pada Februari 2004 yang dibanjiri lebih 30 ribu penonton yang turut mengundangkan kumpulan Godbless dan Awie Wings sebagai pembuka tirai konsert termasuk juga dihadiri Yazit.[27] Setelah konsert itu dijayakan tidak kurang juga para peminat mengkritik tentang ketiadaan Yazit sebagai anggota asal Search. Persembahan konsert bersejarah tersebut itu telah dirakam dalam album live Konsert Rock Search Evolusi 2004 yang keluar tiga tahun kemudian. Setelah itu pada bulan September 2004 Search menjadi artis pembukaan untuk menjayakan konsert Scorpions di Kuala Lumpur yang membentuk jelajah Southeast Asia Unbreakable Tour oleh kugiran Jerman tersebut, walaupun menghadapi tentangan hebat dari Pemuda PAS atas alasan konsert tersebut bakal merosakkan akhlak muda-mudi.[28] Lebih kurang setahun kemudian kemelut Search dan Yazit berakhir di mana Lola (dram) telah mengundurkan diri dari Search dan Yazit adalah selaku pemain dram asal dan pengasas kumpulan Search telah kembali ke ke pangkuan Search setelah Search dan Yazit mendapat kata sepakat untuk kembali berdamai pada tahun 2005. Boleh dikatakan majoriti peminat berpuas hati dengan berita kembalinya Yazit ke ke pangkuan Search. Menurut para peminat juga, Search tidak sesuai atau tidak lengkap jika Yazit tiada di dalam kugiran lagenda pujaan hati mereka.

Ekoran dari kejayaan Amy membuat penyatuan semula bersama Search maka ramai artis yang dulu berkumpulan membuat penyatuan semula bersama kumpulan asal mereka seperti Nash bersama kumpulan Lefthanded, Saleem bersama kumpulan Iklim Awie bersama kumpulan Wings, Mus bersama kumpulan May, Joey bersama kumpulan Bumiputra Rockers, Mael bersama kumpulan XPDC dan ramai lagi.

Pada awal tahun 2006, Kid dan Din telah mengundurkan diri sekali lagi dari Search dan Hillary kembali pada Search setelah sekian lama beliau meninggalkan kumpulan tersebut dari tahun 1988. Petikan bunyi gitar beliau begitu sinonim dengan kumpulan Search dan Cromok, petikan gitar beliau yang 'berhantu' membuatkan peminat masih mahukan Hillary Ang kembali bersama Search dan media mengesahkan bahawa Amy, Nasir, Hillary Ang dan Yazit kembali bersama untuk merakamkan album baharu sekali lagi, di samping memperkenalkan laman sesawang rasmi mereka, Dunia Search. Amy melaporkan bahawa tapak web tersebut dikunjungi 200,000 kali sepanjang minggu pertamanya.[29] Single pertama mereka sejak tujuh tahun menyepi, Ying dan Yang yang boleh dimuat turun dari laman web tersebut, merupakan sebuah single dari EP Empire Garden. Bagaimanapun, EP tersebut tidak dapat dipasarkan atas masalah-masalah teknikal.[8] Serentak dengan Empire Garden, mereka mengusahakan album Gothik Malam Edan yang mengunakn hasil dari Edrie Hashim & M. Nasir yang berjaya diterbitkan pada pertengahan tahun 2006, kali ini di bawah label edaran Life Records dan syarikat rakaman Neo Digital Sdn Bhd.

Pada tahun 2006 juga, Search mengumumkan konsert S2 Celebration sempena ulang tahun mereka yang ke-25, bergandingan dengan kumpulan Slank dari Indonesia, yang dijadualkan berlangsung pada 4 Januari 2007 di Stadium Merdeka. Bagaimanapun, kumpulan Search menarik diri pada saat-saat akhir, kononnya sebagai tanda penghormatan kepada mangsa-mangsa banjir yang melanda Kota Tinggi, Johor pada bulan sebelumnya, maka tinggalnya Slank dengan bantuan kugiran Spider dan Kumpulan Wings. Akibatnya, konsert yang menantikan kehadiran menececah 20,000 peminat menjadi hambar dengan kehadiran 7,000 orang sahaja, dilaporkan kebanyakannya berasal dari Indonesia.[30].Setelah Search membatalkan menyertai konsert S2 Celebration sempena ulang tahun mereka yang ke-25,Search membuat konsert Konsert Selepas Banjir di Johor, selepas banjir besar melanda Kota Tinggi, Johor. Tahun 2007 juga Search telah menjayakan konsert di Planet Hollywood Kuala Lumpur yang menyaksikan 'Full House' pada malam konsert tersebut.

Pada tahun 2008, Amy Search mencuri perhatian media Nusantara dengan meluahkan perasaan tidak senang hati atas kecenderungan stesen radio Malaysia yang seakan-akan mengutamakan lagu Indonesia.[31]

Pada tahun 2009, Search menganjurkan jelajah Konsert Penghargaan Search di Awan Biru yang dilangsungkan di 11 tempat di seluruh negara, termasuk tiga di Malaysia Timur iaitu Seberang Jaya Penang, Johor Bahru Johor, Jengka Pahang, Kuala Terengganu, Alor Setar Kedah, Kota Bahru Kelantan, Kuching Sarawak, Miri Sarawak, Sandakan, Kota Kinabalu Sabah, Tawau Sabah, Kelana Jaya dan Shah Alam Selangor. Dan juga sekembalinya Noordin Taib (gitar irama) pada kepangkuan Search pada tahun 2009. Konsert Jelajah yang menerima sokongan dari penaja utamanya Celcom[32] ini bermula dengan konsert pembukaan di Seberang Perai pada 2 Mei[33] hingga konsert kemuncak di Kuala Lumpur pada 1 Ogos. Konsert kemuncak di Kuala Lumpur pada 1 Ogos menyaksikan kembalinya Kid (gitar utama) pada Search. Konsert istimewa itu menyaksikan dua gitaris di atas pentas iaitu Kid (gitar utama), dan Hillary Ang (gitar utama) selain Noodin (gitar irama). Tugas gitar utama di galas sekali lagi oleh Hillary dan Kid (gitar utama). Konsert terakhir yang dilangsungkan di padang Polo Pavilion, Kelab Ekuestrian, Bukit Kiara Kula Lumpur itu, beberapa hari selepas hari kelahiraan Amy yang ke-50, dilaporkan menarik kira-kira 14,000[34] hingga 25,000[35] peminat. Konsert tersebut ini juga adalah konsert terakhir bagi Hillary (gitar utama) sebelum beliau mengundurkan diri dari Search sekali lagi.